class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:      
        n = len(s)
        if n <= 1 or s[::-1] == s:
            return n

        dp = [0]*n
        for i in range(n-1, -1, -1):
            temp = 0  
            dp[i] = 1            
            for j in range(i+1, n):
                if s[i] == s[j]:
                    temp, dp[j] = dp[j], temp + 2
                else:
                    print(j,i)
                    print(s[i],s[j],temp)
                    temp = dp[j]
                    if dp[j-1] > dp[j]:
                        dp[j] = dp[j-1]
                    print(dp[j])
        return dp[-1]

a="addafda"
a1=Solution()
print(a1.longestPalindromeSubseq(a))